Parallel solver for shifted systems in a hybrid CPU-GPU framework

摘要

This paper proposes a combination of a hybrid CPU--GPU and a pure GPUsoftware implementation of a direct algorithm for solving shifted linearsystems $(A - \sigma I)X = B$ with large number of complex shifts $\sigma$ andmultiple right-hand sides. Such problems often appear e.g. in control theorywhen evaluating the transfer function, or as a part of an algorithm performinginterpolatory model reduction, as well as when computing pseudospectra andstructured pseudospectra, or solving large linear systems of ordinarydifferential equations. The proposed algorithm first jointly reduces thegeneral full $n\times n$ matrix $A$ and the $n\times m$ full right-hand sidematrix $B$ to the controller Hessenberg canonical form that facilitatesefficient solution: $A$ is transformed to a so-called $m$-Hessenberg form and$B$ is made upper-triangular. This is implemented as blocked highly parallelCPU--GPU hybrid algorithm; individual blocks are reduced by the CPU, and thenecessary updates of the rest of the matrix are split among the cores of theCPU and the GPU. To enhance parallelization, the reduction and the updates areoverlapped. In the next phase, the reduced $m$-Hessenberg--triangular systemsare solved entirely on the GPU, with shifts divided into batches. The benefitsof such load distribution are demonstrated by numerical experiments. Inparticular, we show that our proposed implementation provides an excellentbasis for efficient implementations of computational methods in systems andcontrol theory, from evaluation of transfer function to the interpolatory modelreduction.